package org.gap.wizards.utils;

import java.awt.Point;
import java.util.LinkedList;
import java.util.List;

import org.gap.wizards.world.Location;
import org.gap.wizards.world.Movement;

public class AStar {
	private List<Node> open = new LinkedList<Node>();
	private List<Node> closed = new LinkedList<Node>();
	
	private Point destination;
	private Location location;

	public void setLocation(Location location) {
		this.location = location;
	}

	public int size() {
		return open.size();
	}
	
	/**
	 * begins the search from the destination, and works it's way back to the origin.
	 * @param from
	 * @param to
	 * @return
	 */
	public Node findPath(Point from, Point to) {
		open.clear();
		closed.clear();
		setOrigin(from);
		Node currentLocation = createNode(null, null, from);
		open.add(createNode(null, to, from));
		// 1. Check if the end node is reached
		while (stillTryingToReachOurDestination(currentLocation) || areThereMorePathsToTry()) {
			
			// 2. Grab the cheapest node so far
			Node node = getCheapest();
			
			if (node == null || isEqualToOrAdjacentTo(currentLocation, node)) {
				// return node;
				currentLocation = node;
				break;
			}
			
			// 3. Find all it's neighbors and add them to the open list
			findNeigborsAndAddThemToTheOpenList(node);
			// 4. Move the cheapest node to the closed stack.
			moveCheapestNodeToClosedStack(node);
		}
		if (currentLocation == null) {
			return null;
		}
		return currentLocation;
	}

	private boolean isEqualToOrAdjacentTo(Node currentLocation, Node node) {
		for (Movement each : Movement.values()) {
			if (each.adjustLocation(currentLocation.position()).equals(node.position())) {
				return true;
			}
		}
		return node.equals(currentLocation);
	}
	
	private boolean stillTryingToReachOurDestination(Node endNode) {
		return !open.contains(endNode);
	}

	private boolean areThereMorePathsToTry() {
		return !open.isEmpty();
	}

	private boolean moveCheapestNodeToClosedStack(Node node) {
		open.remove(node);
		return closed.add(node);
	}
	
	private Node getCheapest() {
		Node res = null;
		
		for (Node node : open)
		{
			if (res == null) {
				res = node;
			}
			else if (res.cost() > node.cost()) {
				res = node;
			}
		}
		
		return res;
	}

	void findNeigborsAndAddThemToTheOpenList(Node node) {
		int x = node.position().x;
		int y = node.position().y;
		for (int i = x - 1; i <= x + 1; i++ )
			for (int j = y - 1; j <= y + 1; j++) {
				if (i == x && j == y)
					continue;
				addNode(node, i, j);		
			}
	}

	private void addNode(Node parent, int x, int y) {
		if (!location.canMoveTo(new Point(x, y))) {
			return;
		}
		Node node = createNode(parent, new Point(x, y), getDestination());
		
		if (closed.contains(node))
			return;
		else if (open.contains(node))
			return;
		open.add(node);
	}
	
	//*************************************
	// Static members:
	// 
	// Support methods for A* algorithm
	//*************************************
	
	static Node createNode(Node parent, Point to, Point from) {
		if (to == null)
			return new Node(parent, from, 0, 0);
		else {
			int cost = costOf(to, from);
			if (parent == null)
				return new Node(parent, to, 0, cost);
			return new Node(parent, to, parent.cost() + cost, cost);		
		}
	}
	
	/**
	 * Calculates the cost to travel along the x or y axis from orgin to destination in a
	 * 2d environment.
	 * @param origin
	 * @param destination
	 * @return
	 */
	/*package*/ static int costOf(Point origin, Point destination) {
		return 10 * (distance(origin.x, destination.x) + distance(origin.y, destination.y));
	}
	
	/**
	 * Returns the distance between two points on a line.
	 */
	private static int distance(int a, int b) {
		if (a > b)
			return a - b;
		return b - a;
	}

	public void setOrigin(Point destination) {
		this.destination = destination;
	}

	public Point getDestination() {
		return destination;
	}
}
